|
| creator |
Horsch, Martin
| | Kufleitner, Manfred
| | date |
2006-05-23
| | | | description |
17 pages
| |
We compare the expressive power of some first-order fragments and of
two simple temporal logics over Mazurkiewicz traces. Over words,
most of these fragments have the same expressive power whereas over
traces we show that the ability of formulating concurrency increases
the expressive power.
We also show that over so-called dependence structures it is
impossible to formulate concurrency with the first-order fragments
under consideration. Although the first-order fragments
$\Delta_n[<]$ and $FO^2[<]$ over partial orders both can
express concurrency of two actions, we show that in general they are
incomparable over traces. For $FO^2[<]$ we give a
characterization in terms of temporal logic by allowing an operator
for parallelism.
| | format |
application/pdf
| | 178113 Bytes | |